﻿#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


/*
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

 

示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
 

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

*/



class Solution {
public:
	int minPathSum(vector<vector<int>>& grid) {
		int m = grid.size(); int n = grid[0].size();
		vector<vector<int>> dp(m+10,vector<int> (n+10));

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				dp[i][j] = 9999999;
			}
		}

		dp[0][0] = 0;

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (i - 1 >= 0) {
					dp[i][j] = min(dp[i][j], dp[i - 1][j]);
				}
				if (j - 1 >= 0) {
					dp[i][j] = min(dp[i][j], dp[i][j-1]);
				}
				dp[i][j] +=  grid[i][j];
			}
		}

		return dp[m-1][n-1];
	}
};


//
//
//int main() {
//	Solution s;
//	// [[1,3,1],[1,5,1],[4,2,1]]
//	vector<vector<int>> vv{
//		{1,2,3},
//		{4,5,6}	
//	};
//	cout << s.minPathSum(vv);
//
//
//	return 0;
//}





